#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main()
{
	int t = 0;
	scanf("%d", &t);
	int i = 0;
	for (i = 0; i < t; i++)
	{
		int n = 0;
		scanf("%d", &n);
		if (n == 1)
		{
			printf("1\n");
		}
		else if (n == 2)
		{
			printf("2\n");
		}
		else if (n == 3)
		{
			printf("4\n");
		}
		else if(n>=4)
		{
			int a = 1, b = 2, c = 4;
			int num = 0;
			for (n; n > 3; n--)
			{
				num = a + b + c;
				a = b;
				b = c;
				c = num;
			}
			printf("%d\n", num);
		}
	}
	return 0;
}